package code;

public class Code_116 {

    public static void main(String[] args){

        Code_116 code_116 = new Code_116();
        Node root = new Node(1);

        root.left = new Node(2);
        root.right = new Node(3);

        root.left.left = new Node(4);
        root.left.right = new Node(5);

        root.right.left = new Node(6);
        root.right.right = new Node(7);


        root.left.left.left = new Node(8);
        root.left.left.right = new Node(9);

        root.left.right.left = new Node(10);
        root.left.right.right = new Node(11);

        root.right.left.left = new Node(12);
        root.right.left.right = new Node(13);

        root.right.right.left = new Node(14);
        root.right.right.right = new Node(15);

        code_116.connect(root);

    }

    public Node connect(Node root) {
        if(root == null){
            return root;
        }

        setNodeNull(root);

        return root;
    }

    // node 每一层的头节点
    public void setNodeNull(Node node){
        if(node == null){
            return;
        }

        Node rightNode = null, leftNode = null, indexNode = node, rowTopNode = null;

        // 对当前层进行遍历获取，左边最右节点，右边最左节点
        while(indexNode != null){

            //对此节点进行子节点的null设置
            setChildNode(indexNode);

            // 获取第一行最左边节点
            if(rowTopNode == null){
                // 当前遍历节点有左右节点
                if(indexNode.left != null){
                    rowTopNode = indexNode.left;
                }else if(indexNode.right != null){
                    rowTopNode = indexNode.right;
                }else{
                    //遍历下一个节点
                    indexNode = indexNode.next;
                    continue;
                }
            }

            // 获取左节点最右边节点
            if(rightNode == null){
                // 当前遍历节点有左右节点
                if(indexNode.right != null){
                    rightNode = indexNode.right;
                }else if(indexNode.left != null){
                    rightNode = indexNode.left;
                }
                //遍历下一个节点
                indexNode = indexNode.next;
                continue;
            }

            // 获取右节点最左边节点
            if(leftNode == null){
                // 当前遍历节点有左右节点
                if(indexNode.left != null){
                    leftNode = indexNode.left;
                }else if(indexNode.right != null){
                    leftNode = indexNode.right;
                }else{
                    //遍历下一个节点
                    indexNode = indexNode.next;
                    continue;
                }
            }

            // 对获取到的节点进行next
            if(rightNode != null && leftNode != null){
                rightNode.next = leftNode;
                rightNode = null;
                leftNode = null;
                //遍历下一个节点
            //    indexNode = indexNode.next;
            }
        }

        //接着处理下一层的头节点
        if(rowTopNode != null){
            setNodeNull(rowTopNode);
        }
    }

    public void setChildNode(Node node){
        if(node == null){
            return;
        }

        //对左右子节点进行填充 null
        if(node.left != null && node.right != null && node.left.next == null){
            node.left.next = node.right;
        }
    }


}
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

